#include "LinkList.h"
#include <iostream>

// 构造函数
LinkList::LinkList() : size(0)
{
    head = new Node(0); // 头节点
}

// 拷贝构造
LinkList::LinkList(const LinkList &list)
{
    size = 0;
    head = new Node(0);
    Node *travelPoint = list.head->next;
    while (travelPoint != nullptr)
    {
        InsertTail(travelPoint->value);
        travelPoint = travelPoint->next;
    }
}

// 析构函数
LinkList::~LinkList()
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 记录下一个节点指针
        delete head;                 // 放掉当前指针
        head = nextNode;             // head指针往后走
    }
}

// 尾插法
void LinkList::InsertTail(const ElementType &element) // O(n)
{
    Node *travelPoint = head; // 遍历指针
    // 找尾巴
    while (travelPoint->next != nullptr)
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->next = new Node(element); // 在尾部插入新的节点
    size++;
}

// 头插法
void LinkList::InsertHead(const ElementType &element) // O(1)
{
    Node *newNode = new Node(element);
    newNode->next = head->next;
    head->next = newNode;
    size++;
}

// 中间插入
void LinkList::InsertByIndex(int index, const ElementType &element)
{
    if (index < 0 || index > size)
        return;
    Node *travelPoint = head;
    for (int i = 0; i < index; i++) // index-1
    {
        travelPoint = travelPoint->next;
    }
    Node *newNode = new Node(element);
    newNode->next = travelPoint->next;
    travelPoint->next = newNode;
    size++;
}

// 按位置删除
void LinkList::RemoveByIndex(int index) // O(n)
{
    if (index < 0 || index >= size)
        return;
    Node *travelPoint = head;
    for (int i = 0; i < index; i++) // index-1
    {
        travelPoint = travelPoint->next;
    }
    Node *freeNode = travelPoint->next;
    travelPoint->next = freeNode->next;
    delete freeNode;
    size--;
}

// 按值删除
void LinkList::RemoveByElement(const ElementType &element)
{
    Node *travelPoint = head;
    while (travelPoint->next != nullptr)
    {
        if (travelPoint->next->value == element)
        {
            Node *freeNode = travelPoint->next;
            travelPoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
            travelPoint = travelPoint->next;
    }
}

// 按位置修改
void LinkList::UpdateByIndex(int index, const ElementType &element) // O(n)
{
    if (index < 0 || index >= size)
        return;
    Node *travelPoint = head;
    for (int i = 0; i <= index; i++) // index-1
    {
        travelPoint = travelPoint->next;
    }
    travelPoint->value = element;
}

// 按值修改
void LinkList::UpdateByElement(const ElementType &oldvalue, const ElementType &newvalue)
{
    Node *travelPoint = head->next;
    while (travelPoint != nullptr)
    {
        if (travelPoint->value == oldvalue)
            travelPoint->value = newvalue;
        travelPoint = travelPoint->next;
    }
}

// 冒泡排序
void LinkList::BubbleSort()
{
    for (int i = 0; i < size - 1; i++)
    {
        Node *travelPoint = head; // 从头开始扫描链表
        for (int j = 0; j < size - i - 1; j++)
        {
            if (travelPoint->next->value > travelPoint->next->next->value)
            {
                Node *prevNode = travelPoint->next;
                Node *nextNode = prevNode->next;
                travelPoint->next = nextNode;
                prevNode->next = nextNode->next;
                nextNode->next = prevNode;
            }
            travelPoint = travelPoint->next;
        }
    }
}

// 归并
LinkList LinkList::Merge(const LinkList &list)
{
    LinkList result;
    Node *p1 = head->next;
    Node *p2 = list.head->next;
    while (p1 && p2)
    {
        if (p1->value < p2->value)
        {
            result.InsertTail(p1->value);
            p1 = p1->next;
        }
        else
        {
            result.InsertTail(p2->value);
            p2 = p2->next;
        }
    }
    while (p1)
    {
        result.InsertTail(p1->value);
        p1 = p1->next;
    }
    while (p2)
    {
        result.InsertTail(p2->value);
        p2 = p2->next;
    }
    return result;
}

// 排序
void LinkList::Sort()
{
    FastSort(head->next, nullptr);
}

// 链表逆序
void LinkList::Reserve()
{
    Node *prev = nullptr;
    Node *cur = head->next;
    Node *Next = cur->next;
    while (Next != nullptr)
    {
        cur->next = prev; // 逆序
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev; // 最后一个节点单独逆序
    head->next = cur;
}

void LinkList::Reserve2()
{
    head->next = Reserve2(head->next);
}

// 显示
void LinkList::show()
{
    // std::cout<<"size:"<<size<<std::endl;
    Node *travelPoint = head->next; // 存有效数据的第一个节点
    while (travelPoint != nullptr)  // 当前节点存在
    {
        std::cout << travelPoint->value << " "; // 打印数据域
        travelPoint = travelPoint->next;        // 访问下一个节点
    }
    std::cout << std::endl;
}

// 判断是否是回文结构
bool LinkList::IsPalindrome()
{
    // 1. 找到链表的中点
    Node *slow = head;
    Node *fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2. 反转链表的后半部分
    Node *prev = nullptr;
    Node *cur = slow->next;
    Node *Next = cur->next;
    while (Next != nullptr)
    {
        cur->next = prev; // 逆序
        prev = cur;
        cur = Next;
        Next = cur->next;
    }
    cur->next = prev; // 最后一个节点单独逆序

    // 3. 比较前半部分和反转后的后半部分
    Node *firstHalf = head->next;
    while (cur)
    {
        if (firstHalf->value != cur->value)
        {
            return false;
        }
        firstHalf = firstHalf->next;
        cur = cur->next;
    }
    return true;
}

// 快速排序(快慢指针法)
void LinkList::FastSort(Node *start, Node *end)
{
    if (start == end)
        return;
    Node *temp = start;       // 基准值指针
    Node *slow = start;       // 慢指针
    Node *fast = start->next; // 快指针
    while (fast != end)
    {
        // 快指针所指数据比基准值小
        if (fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(fast->value, slow->value);
        }
        fast = fast->next;
    }
    std::swap(temp->value, slow->value);
    FastSort(start, slow);
    FastSort(slow->next, end);
}

// 递归逆序
LinkList::Node *LinkList::Reserve2(Node *node)
{
    // 返回值是新链表的头
    // 终止条件
    if (node->next == nullptr) // 原来的尾巴是新的头
        return node;
    else
    {
        Node *newHeader = Reserve2(node->next);
        node->next->next = node; // 逆序
        node->next = nullptr;    // 新尾巴next指针指向空
        return newHeader;
    }
}
